/*
    created: 2023/4/18
    filename: treelist.c
    author: 李东霖
    purpose：二叉树的链式存储

*/
#include"treelist.h"

//采用括号表示法创建二叉树  
int CreateBTree(BTree* tree,char *str)
{
    if(*tree != NULL || str == NULL) return -1; 
    BTNode* p;
    int k;
    //写一个简易的栈  
    BTNode* stack[MAXSIZE];
    int top = -1;
    int pos = 0;
    char *ch = str;
    while(*ch != '\0')
    {
        switch (*ch)
        {
            //遇到左括号，说明下一个是他的左孩子 把他进栈
        case '(':
        {
            ++top;
            stack[top] = p;
            k = 1;
            break;
        }
        //当前结点的左右都已经处理完了，该结点退栈
        case ')':
        {
            --top;
            break;
        }
        //下一个是这一层的兄弟结点，改变k值
        case ',':
        {
            k = 2;
            break;
        }   
        default:
        {
            p = (BTNode*)malloc(sizeof(BTNode));
            p->data = *ch;
            p->lchild = p->rchild = NULL;
            if(*tree == NULL)*tree = p;
            else
            {
                switch(k)
                {
                    case 1:stack[top]->lchild = p;break;
                    case 2:stack[top]->rchild = p;break;
                }
            }
            break;
        }
            
        }
    ++ch;
    }
    return 0;
}
//销毁二叉树  
void DestroyBTree(BTree* tree)
{
    if(*tree == NULL) return;
    DestroyBTree(&(*tree)->lchild);
    DestroyBTree(&(*tree)->rchild);
    free(*tree);
    *tree = NULL;
}
//查找结点 
BTNode* FindNode(BTree tree,ElemType *elem)
{
    BTNode* p;
    if(elem == NULL || tree == NULL) return NULL;
    if(tree->data == *elem) return tree;
    else
    {
        //找他的左子树 
        p = FindNode(tree->lchild,elem);
        if(p!=NULL) return p;
        //没找到找他的右子树
        else return FindNode(tree->rchild,elem);
    }
}
//查找该结点的子节点
BTNode* LchildNode(BTNode* Node)
{
    return Node->lchild;
}
BTNode* RchildNode(BTNode* Node)
{
    return Node->rchild;
}
//求这棵树的高度 
int TreeHight(BTree tree)
{
    if(tree == NULL) return 0;
    int ll = TreeHight(tree->lchild);
    int rr = TreeHight(tree->rchild);
    return ll>rr ? ll+1 : rr+1;
}
//输出二叉树,这是一个括号表示法   
void DispTree(BTree tree)
{
    if(tree == NULL) return;
    //先放入这个数组  
    printf("%c",tree->data);
    //它存在子结点
    if(tree->lchild != NULL || tree->rchild != NULL)
    {
        printf("(");
        DispTree(tree->lchild);
        if(tree->rchild != NULL)
        {
            printf(",");
        }
        DispTree(tree->rchild);
        printf(")");
    }
}


//层次遍历
void LevelOrder(BTree tree)
{
    if(tree == NULL ) return;
    //这里需要一个循环队列  
    BTNode* data[MAXSIZE];
    int front = 0;
    int rear = 0;
    BTNode* elem = tree;
    //进栈根结点
    data[rear] = elem;
    rear = (rear+1)%MAXSIZE;    
    while(front != rear)
    {
        //出栈一个元素
        memcpy(&elem,data+front,sizeof(elem));
        printf("%c",elem->data);
        front = (front+1)%MAXSIZE;

        //将出队元素的左子树右子树入队
        if((rear+1)%MAXSIZE == front) return;  //队满
        if(elem->lchild != NULL)
        {
            memcpy(data+rear,&elem->lchild,sizeof(BTNode*));
            rear = (rear+1)%MAXSIZE;   
        }
        
        if((rear+1)%MAXSIZE == front) return;  //队满
        if(elem->rchild != NULL)
        {
            memcpy(data+rear,&elem->rchild,sizeof(BTNode*));
            rear = (rear+1)%MAXSIZE;   
        } 
    }
}


//先序遍历  
void PreOrder(BTree tree)
{
    if(tree == NULL) return;
    printf("%c",tree->data);
    PreOrder(tree->lchild);
    PreOrder(tree->rchild);

}
//中序遍历  
void InOrder(BTree tree)
{
    if(tree == NULL) return;
    
    InOrder(tree->lchild);
    printf("%c",tree->data);
    InOrder(tree->rchild);

}
//后序遍历  
void PostOrder(BTree tree)
{
    if(tree == NULL) return;
    PostOrder(tree->lchild);
    PostOrder(tree->rchild);
    printf("%c",tree->data);
}




